package com.ocean.dynamic;

/**
 * https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/
 *
 * @author linmiaolai@sanyygp.com<br>
 * @version 1.0<br>
 * @date 2023/03/13 <br>
 */
public class BestTimeToBuyAndSellStock {
    public static void main(String[] args) {
        BestTimeToBuyAndSellStock sellStock = new BestTimeToBuyAndSellStock();
        int[] nums = {7, 1, 5, 3, 6, 4};
        int res = sellStock.maxProfit2(nums);
        System.out.println(res);
    }

    public int maxProfit(int[] prices) {
        //dp[i]表示截止到i，价格的最低点是多少   dp[i]=min(dp[i-1],nums[i])
        int max = 0;
        int[] dp = new int[prices.length];
        dp[0] = prices[0];
        for (int i = 1; i < prices.length; i++) {
            dp[i] = Math.min(dp[i - 1], prices[i]);
            max = (prices[i] - dp[i]) > max ? prices[i] - dp[i] : max;
        }
        return max;
    }

    public int maxProfit2(int[] prices) {
        //dp[i]表示截止到i，价格的最低点是多少   dp[i]=min(dp[i-1],nums[i])
        int max = 0;
        int minPrice = Integer.MAX_VALUE;
        for (int i = 0; i < prices.length; i++) {
            minPrice = Math.min(minPrice, prices[i]);
            max = Math.max((prices[i] - minPrice), max);
        }
        return max;
    }
}
